package leecode

// MyQueueLCR 维护一个最大值队列
type MyQueueLCR struct {
	queue []int
}

// NewQueueLCR 初始化队列
func NewQueueLCR() *MyQueueLCR {
	return &MyQueueLCR{queue: make([]int, 0)}
}

// 取出队列中第一个元素
func (m *MyQueueLCR) front() int {
	return m.queue[0]
}

// 移除队列中的元素
func (m *MyQueueLCR) pop(val int) {
	if len(m.queue) > 0 && val == m.front() {
		m.queue = m.queue[1:]
	}
}

// 元素进入队列
func (m *MyQueueLCR) push(value int) {
	for len(m.queue) > 0 && value > m.queue[len(m.queue)-1] {
		m.queue = m.queue[:len(m.queue)-1]
	}
	m.queue = append(m.queue, value)
}

func maxAltitude(heights []int, limit int) (result []int) {
	if len(heights) < 1 {
		return
	}
	queue := NewQueueLCR()
	//初始化窗口
	for i := 0; i < limit; i++ {
		queue.push(heights[i])
	}
	//取得第一个窗口中的最大值
	result = append(result, queue.front())
	for right := limit; right < len(heights); right++ {
		//移除队列中的第一个元素
		queue.pop(heights[right-limit])
		//向队列中追加元素
		queue.push(heights[right])
		//获取最大值
		result = append(result, queue.front())
	}
	return result
}
